import java.util.ArrayList;
import java.util.List;

public class Test13 {
    //定义全局变量 ret 用来收集结果
    List<List<Integer>> ret;//用集合来表示二维数组
    List<Integer> path;//用来保存每一次结果
    boolean[] check;//用来表示某个元素是不是已经被选取过

    public List<List<Integer>> permute(int[] nums) {
        //1.初始化
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        //2.调用dfs(回溯的核心)
        dfs(nums);
        return ret;
    }

    public void dfs(int[] nums) {
        //1.当path的长度和nums的长度一样，那么就是将nums的所有元素已经排列在path里
        if (nums.length == path.size()) {
            ret.add(new ArrayList<>(path));
            return;
        }
        //每一次都有3个选择，只是符不符合的问题
        for (int i = 0; i < nums.length; i++) {
            //正面这个元素还没选取
            if (check[i] == false) {
                path.add(nums[i]);//将这个元素添加到数组中
                /*
                check还能这么理解：如果一个check的元素为true，也就是来到树的第一层（看上图，有层数注解）
                                有两个check的元素为true，也就是来到树的第二层
                                有三个check的元素为true，也就是来到树的第三层
                 */
                check[i] = true;//将当前位置的元素标记为true，表示已经被选取过了
                dfs(nums);
                check[i] = false;//将当前位置改为还未选择，具体解析看上图
                path.remove(path.size() - 1);//移除最后一个元素
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        Test13 test13 = new Test13();
        test13.permute(a);
        for(int i = 0;i < test13.ret.size();i++){
            System.out.println(test13.ret.get(i));
        }
    }

}
